import java.util.ArrayList;
import java.util.LinkedList;


public class Utility{
	 public StaticMap globalMap;
	 public int boardW;
	 public int boardH;
	 //private int[][] utilityArrowMatrix;
	 private int[][] utilityNumberMatrix;
	 private int[][] goalMatrix;
	 public UtilityList utilityNumberList;
	 //public ArrayList<int[][]> utilityArrowList;
	 private int goalcount;
	 private TileList goalList;
	 //private BoxList boxList;
	//constructor
	 private LinkedList<Integer> activeGoalList = new LinkedList<Integer>();

	 public Utility(StaticMap Map, TileList list)
	 {
		 globalMap=Map;
		 goalcount=list.size();
		 boardW=globalMap.boardW;
		 boardH=globalMap.boardH;
		 goalList=list;
		 utilityNumberMatrix=new int[boardW][boardH];
		 utilityNumberList=new UtilityList();
		 
		 goalMatrix = new int[boardW][boardH];
		 
		 for (int i=0 ; i<goalcount ; i++) {
			 Coord goalCoord = goalList.get(i);
			 goalMatrix[goalCoord.x][goalCoord.y] = i;
		 }

		 for (int i=0;i<goalcount;i++)
		 {
			 activeGoalList.addFirst(i);
			 
			 utilityNumberMatrix=new int[boardW][boardH];
			 for(int xx=0;xx<boardW;xx++)
			 {
				 for(int yy=0;yy<boardH;yy++)
				 {
					 utilityNumberMatrix[xx][yy]=9999;
			         //utilityNumberMatrix[i][j].x=9999;
				 }
			 }
			 utilityNumberList.add(utilityNumberMatrix);
		 }
		 
		 
	 }
	 
	    private static final char NIL   = 'x';
		private static final char U     = 'U';
		private static final char D     = 'D';	
		private static final char R     = 'R';
		private static final char L     = 'L';
		private static final char u     = 'u';
		private static final char d     = 'd';	
		private static final char r     = 'r';
		private static final char l     = 'l';	
	 
	 private boolean isTileInsideMatrix(Coord c, char lastInstruction) {
			switch(lastInstruction) {
			case u :
			case U : return (c.y >= 0); 
			case r :
			case R : return (c.x < globalMap.boardW); 
			case d :
			case D : return (c.y < globalMap.boardH); 
			case l :
			case L : return (c.x >= 0); 
			default: 
				System.err.println("Incorrect instruction");
				return false;
			}
		}
	 
	
	public void fillNumbersBfs(int x, int y,int number,int i)
	{
		
		//for the position i am right now, i give it a value and to which goal pertains to
		utilityNumberList.get(i)[x][y]=number;
		
		
		//Initialise all variables
		LinkedList<Coord> queueBFS = new LinkedList<Coord>();		
		Coord currentTile = null;		
		Coord nextTile = null;
		//Start at the current position of the Player
		queueBFS.add(BoxMap.getBox(x, y).getCoord());		

		//BFS loop
		while(!queueBFS.isEmpty()) {
			currentTile = queueBFS.removeFirst();
			WalkingCoord.set(currentTile);
			
			number=utilityNumberList.get(i)[currentTile.x][currentTile.y];
			number++;
			
			//Loop through the instructions: Up, Right, Down, Left: u,r,d,l
			for (char currentInstruction : Constants.getAllDirections()) {
				
				//Retrieve the next tile from the instruction
				
				//nextTile = currentTile.getCoordFromDirection(currentInstruction);
				nextTile = WalkingCoord.getFromDirection(currentInstruction);
				
				//Check that the tile is inside boundaries, is empty, and is not the startpos
				
				if (nextTile!=null && isTileInsideMatrix(nextTile, currentInstruction)&&
						(!globalMap.isTileWall(nextTile)))
						{
 							if(utilityNumberList.get(i)[nextTile.x][nextTile.y]>number){
								//System.out.println("SCREAM UTILITY "+number+" "+nextTile.x+","+nextTile.y);
								//for the position i am right now, i give it a value and to which goal pertains to
								//if(globalMap.isTileTunnel(nextTile))number-=1;
 								utilityNumberList.get(i)[nextTile.x][nextTile.y]=number; 
 								number+=1;
								//queueBFS.add(new Coord(nextTile));	
								queueBFS.add(BoxMap.getBox(nextTile).getCoord());
							}

	
						}
		
			}
		}
		

		
		
	}
	
	
	
	
	public void updateUtilityNumber(Box boxBefore, Box boxAfter)
	{
		int goalFill;
		Coord before = boxBefore.getCoord();
		Coord after=boxAfter.getCoord();
		
				
		
		if(goalMatrix[before.x][before.y]==0){//before we were not in a goal
			if(goalMatrix[after.x][after.y]!=0){//now we are in a goal
				//Turn off the "After"-goal
				
				goalFill = goalMatrix[after.x][after.y];
				activeGoalList.removeFirstOccurrence(goalFill);
			}
		}
		
		if(goalMatrix[before.x][before.y]!=0){//before we were in a goal
			if(goalMatrix[after.x][after.y]==0){//now we are NOT in a goal
				//Turn on the "Before"-goal
				
				goalFill = goalMatrix[before.x][before.y];
				activeGoalList.addFirst(goalFill);
			}
		}
		
		if(goalMatrix[before.x][before.y]==0){//before we were in a goal
			if(goalMatrix[after.x][after.y]==0){//now we are in another goal
				//Turn on the "Before"-goal
				goalFill = goalMatrix[before.x][before.y];
				activeGoalList.addFirst(goalFill);	
				
				//Turn off the "After"-goal
				goalFill = goalMatrix[after.x][after.y];
				activeGoalList.removeFirstOccurrence(goalFill);
			}
		}
		

		
		
		
		
		
	/*	if (goalMatrix[c.x][c.y] == 0) turnOn = true;
		
		
		if (goalMatrix[c.x][c.y] != 0) {
			int goalFill = goalMatrix[c.x][c.y];
			
			if (turnOn)
				activeGoalList.addFirst(goalFill);
			if (!turnOn) 
				activeGoalList.removeFirstOccurrence(goalFill);
		}
		*/

		
		
		/*
		for(int i=0;i<boardW;i++)
			 for(int j=0;j<boardH;j++){
				 minimum=1000;
				 
				 if(utilityNumberList.get(0)[i][j].x!=9999 ){
					 
					 for (int goal : activeGoalList) {
						if(minimum>utilityNumberList.get(goal)[i][j].x) {
							minimum= utilityNumberList.get(goal)[i][j].x;
							parentGoal=utilityNumberList.get(goal)[i][j].y;
						}
					 }
					 utilityNumberMatrix[i][j].x=minimum;
					 utilityNumberMatrix[i][j].y=parentGoal;	 

				 }
					 
				 
			 }*/
	
		
	}
	
	/*public int isGoal(Coord c)
	{
		if(utilityNumberMatrix[c.x][c.y].x < 0)
			return utilityNumberMatrix[c.x][c.y].y;
		return 9999;
		
	}*/
	
	private static final int GOALUTILITYVALUE = -1;
	private static final int GOALUTILITYCORNER = -50;
	private static final int GOALUTILITYWALL = -10;
	
	private int setToGoal(Coord c) {
		WalkingCoord.set(c);
		/*
		Coord cN = c.getNorthCoord();
		Coord cE = c.getEastCoord();
		Coord cS = c.getSouthCoord();
		Coord cW = c.getWestCoord();
		*/
		int val;
		if (globalMap.isTileWall(WalkingCoord.getWest())) {
			if (globalMap.isTileWall(WalkingCoord.getNorth())||(globalMap.isTileWall(WalkingCoord.getSouth()))) {
				
				val = GOALUTILITYCORNER;
				//System.out.println("Single corner goal:");
				//WalkingCoord.getCurrent().print();
				
				if (globalMap.isTileGoal(WalkingCoord.getNorth())||(globalMap.isTileGoal(WalkingCoord.getSouth()))) {
					//System.out.println("WallWest, NS goal:");
					//WalkingCoord.getCurrent().print();
					val *= 5;
				}
					
				if (globalMap.isTileGoal(WalkingCoord.getEast()) ) {
					//System.out.println("Corner goal:");
					//WalkingCoord.getCurrent().print();
					val *= 5;
				}
					
				
				return val;
			}
		}
		WalkingCoord.getInitial();
		if (globalMap.isTileWall(WalkingCoord.getEast())) {
			if (globalMap.isTileWall(WalkingCoord.getNorth())||(globalMap.isTileWall(WalkingCoord.getSouth()))) {
				val = GOALUTILITYCORNER;
				
				if (globalMap.isTileGoal(WalkingCoord.getNorth())||(globalMap.isTileGoal(WalkingCoord.getSouth()))){ 
					//System.out.println("WallEast, NS goal:");
					//WalkingCoord.getCurrent().print();
					val *= 5;
				}
				
				if (globalMap.isTileGoal(WalkingCoord.getWest()) ) {
					//System.out.println("Corner goal:");
					//WalkingCoord.getCurrent().print();
					val *= 5;
				}
				
				return val;
			}
		}
		WalkingCoord.getInitial();
		for (int i=0 ; i<4 ; i++) {
			if (globalMap.isTileWall(WalkingCoord.getNext())) {
				return GOALUTILITYWALL;
			}
		}
		/*
		if (globalMap.isTileWall(cW)) {
			if (globalMap.isTileWall(cN)||(globalMap.isTileWall(cS))) {
				return GOALUTILITYCORNER;
			}
		}
		if (globalMap.isTileWall(cE)) {
			if (globalMap.isTileWall(cN)||(globalMap.isTileWall(cS))) {
				return GOALUTILITYCORNER;
			}
		}*/
		return GOALUTILITYVALUE;
	}
	
	private void handleBoxesOnGoalTiles(BoxList boxes) {
		for (Box box : boxes) {
			for (int i=0 ; i<goalcount ; i++) {
				Coord goalCoord = goalList.get(i);
				if (goalCoord.isItSameCoord(box.getCoord())) {
					activeGoalList.removeFirstOccurrence(i);
				}
			}
		}
	}
	
	public void fillUtilityNumbers(BoxList initialBoxes)
	{
		Coord position;
		//if(position)
		
		
		
		
		int number=0;
		for(int i=0;i<goalcount;i++)
		{		
			position=goalList.get(i);
			number=setToGoal(position);
			fillNumbersBfs(position.x,position.y,number,i);
		}
		
		handleBoxesOnGoalTiles(initialBoxes);
		
		//int minimum=-GOALUTILITYVALUE*100;
		//int parentGoal=0;
		
		/*
		for(int i=0;i<boardW;i++)
		{
			 for(int j=0;j<boardH;j++){
				 minimum=1000;
				 
				 if(utilityNumberList.get(0)[i][j].x!=9999)
				 {
					 //for(int goal=0;goal<activeGoalList.size() ;goal++)
					 for (int goalIndex : activeGoalList) {

						if(minimum>utilityNumberList.get(goalIndex)[i][j].x) {
							minimum= utilityNumberList.get(goalIndex)[i][j].x;
							parentGoal=utilityNumberList.get(goalIndex)[i][j].y;
						}
						 
					 }
					 utilityNumberMatrix[i][j].x=minimum;
					 utilityNumberMatrix[i][j].y=parentGoal;
				 } 
			 }
		}	 
		*/
		//return utilityNumberMatrix;
	}
	 
	public int whatIsMyUtility(BoxList boxlist)
	{
		int utility=0;
		int minimum;
		
		//for(int i=0;i<boxlist.size();i++)
		for (Box box : boxlist) {
		
			minimum = 1000;
			Coord c = box.position;
			

			
			for (int goalIndex : activeGoalList) {
				if(minimum>utilityNumberList.get(goalIndex)[c.x][c.y]) {
					minimum= utilityNumberList.get(goalIndex)[c.x][c.y];
				}
			}
			
			//Touch this if you want to penalize walls
			if (StaticMap.getStaticMap().isAdjacentToWallTile(c)) 
				minimum +=0;
			
			//The glorious function
			int fX = 5000000*minimum - minimum*minimum; 
			utility += fX;
			//utility+=utilityNumberMatrix[boxlist.get(i).position.x][boxlist.get(i).position.y].x;
				
		}
		//System.out.println(utility);
		return utility;
		
	}
	
	

	public void print ()
	{

		for (int i=0;i<boardW;i++) {		
			for (int j=0;j<boardH;j++){
				if (!globalMap.isTileWall(new Coord(i,j))) {
				
				int minimum=1000;
				 
				 if(utilityNumberList.get(0)[i][j]!=9999)
					 {
						 //for(int goal=0;goal<activeGoalList.size() ;goal++)
						 for (int goalIndex : activeGoalList) {
	
							if(minimum>utilityNumberList.get(goalIndex)[i][j]) {
								minimum= utilityNumberList.get(goalIndex)[i][j];
								//parentGoal=utilityNumberList.get(goalIndex)[i][j].y;
							}
							 
						 }
						 //System.out.print(minimum);
					 } 
				}
			}		
		}
		
	}
	 
}
